# LeetCode 224、基本计算器
# 一、题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
1 <= s.length <= 3 * 105s由数字、'+'、'-'、'('、')'、和' '组成s表示一个有效的表达式
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 基本计算器（ LeetCode 224 ）:https://leetcode-cn.com/problems/basic-calculator
class Solution {
public int calculate(String s) {
// 使用栈来储存字符串表达式中的数字
Stack<Integer> stack = new Stack<Integer>();
// 为了方便计算，所有的操作都视为加法操作
// 那么原先的减法操作就相当于是加一个负数
// 默认都是正数
int sign = 1;
// 保存计算的结果
int res = 0;
// 获取字符串的长度，然后获取里面的每个字符
int length = s.length();
// 获取字符串里面的每个字符
for (int i = 0; i < length; i++) {
// 获取此时的字符
char ch = s.charAt(i);
// 如果当前字符是数字的话
if (Character.isDigit(ch)) {
// 那么可以通过 - '0' 这个操作把字符转换为整数
// 相当于转换成了 ascii 码进行的数字运算
int value = ch - '0';
// 去查看当前字符的后一位是否存在
// 如果操作并且后一位依旧是数字，那么就需要把后面的数字累加上来
while (i + 1 < length && Character.isDigit(s.charAt(i + 1))){
// i 向后移动，直到遇到非数字为止
i++;
// i 每向后移动一位，当前的值就需要乘以 10
// 比如 s 为 "123+456"
// 此时 i = 0，那么 value 为 1
// i = 1，那么 value 为 1 * 10 + 2 = 12
// i = 2，那么 value 为 12 * 10 + 3 = 123
value = value * 10 + s.charAt(i) - '0';
}
// 那么把获取到的数累加到结果 res 上
res = res + sign * value;
// 如果是 '+'
} else if (ch == '+') {
// 那么说明直接加一个正数
sign = 1;
// 如果是 '-'
} else if (ch == '-') {
// 那么说明加一个负数
sign = -1;
// 如果是 '('
} else if (ch == '(') {
// 根据数学计算规则，需要先计算括号里面的数字
// 而什么时候计算呢？
// 遇到 ) 为止
// 所以，在遇到 ) 之前需要把之前计算好的结果存储起来再计算
// ( ) 直接的计算规则和一开始是一样的
// 1、先把 ( 之前的结果存放到栈中
stack.push(res);
// 2、重新初始化 res 为 0
res = 0;
// 3、把 ( 左边的操作符号存放到栈中
// 比如如果是 5 - （ 2 + 3 ） ，那么就是把 -1 存放进去
// 比如如果是 5 +（ 2 + 3 ） ，那么就是把 1 存放进去
stack.push(sign);
// 4、为了方便计算，所有的操作都视为加法操作
// 那么原先的减法操作就相当于是加一个负数
// 默认都是正数
sign = 1;
// 如果是 ')'
} else if (ch == ')') {
// 那么就需要把栈中存放的元素取出来了
// 在 ch == '（' 这个判断语句中，每次都会往栈中存放两个元素
// 1、先存放左括号外面的结果
// 2、再存放左括号外面的符号
// 1、先获取栈顶元素，即左括号外面的符号，查看是 + 还是 -
int formerSign = stack.peek();
// 把栈顶元素弹出
stack.pop();
// 2、再获取栈顶元素，即左括号结果
int formerRes = stack.peek();
// 把栈顶元素弹出
stack.pop();
// 那结果就是括号外面的结果 + 括号里面的结果，至于是加正数还是负数，取决于左括号外面的符号
res = formerRes + formerSign * res ;
}
}
// 返回计算好的结果
return res;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 基本计算器（ LeetCode 224 ）:https://leetcode-cn.com/problems/basic-calculator
class Solution {
public:
int calculate(string s) {
// 使用栈来储存字符串表达式中的数字
stack<int> st;
// 为了方便计算，所有的操作都视为加法操作
// 那么原先的减法操作就相当于是加一个负数
// 默认都是正数
int sign = 1;
// 保存计算的结果
int res = 0;
// 获取字符串的长度，然后获取里面的每个字符
int length = s.length();
// 获取字符串里面的每个字符
for(int i = 0;i < length;i++){
// 获取此时的字符
char ch = s[i];
// 如果当前字符是数字的话
if( ch >= '0' && ch <= '9' ) {
// 那么可以通过 - '0' 这个操作把字符转换为整数
// 相当于转换成了 ascii 码进行的数字运算
long value = ch - '0';
// 去查看当前字符的后一位是否存在
// 如果操作并且后一位依旧是数字，那么就需要把后面的数字累加上来
while (i + 1< length &&s[i+1]>='0'&&s[i+1]<='9'){
// i 向后移动，直到遇到非数字为止
i++;
// i 每向后移动一位，当前的值就需要乘以 10
// 比如 s 为 "123+456"
// 此时 i = 0，那么 value 为 1
// i = 1，那么 value 为 1 * 10 + 2 = 12
// i = 2，那么 value 为 12 * 10 + 3 = 123
value = value*10 + s[i] - '0';
}
// 那么把获取到的数累加到结果 res 上
res = res + sign * value;
// 如果是 '+'
}else if(ch == '+'){
// 那么说明直接加一个正数
sign = 1;
// 如果是 '-'
}else if(ch == '-'){
// 那么说明加一个负数
sign = -1;
// 如果是 '('
}else if(ch == '('){
// 根据数学计算规则，需要先计算括号里面的数字
// 而什么时候计算呢？
// 遇到 ) 为止
// 所以，在遇到 ) 之前需要把之前计算好的结果存储起来再计算
// ( ) 直接的计算规则和一开始是一样的
// 1、先把 ( 之前的结果存放到栈中
st.push(res);
// 2、重新初始化 res 为 0
res = 0;
// 3、把 ( 左边的操作符号存放到栈中
// 比如如果是 5 - （ 2 + 3 ） ，那么就是把 -1 存放进去
// 比如如果是 5 +（ 2 + 3 ） ，那么就是把 1 存放进去
st.push(sign);
// 4、为了方便计算，所有的操作都视为加法操作
// 那么原先的减法操作就相当于是加一个负数
// 默认都是正数
sign = 1;
// 如果是 ')'
}else if(ch == ')'){
// 那么就需要把栈中存放的元素取出来了
// 在 ch == '（' 这个判断语句中，每次都会往栈中存放两个元素
// 1、先存放左括号外面的结果
// 2、再存放左括号外面的符号
// 1、先获取栈顶元素，即左括号外面的符号，查看是 + 还是 -
int formerSign = st.top();
// 把栈顶元素弹出
st.pop();
// 2、再获取栈顶元素，即左括号结果
int formerRes = st.top();
// 把栈顶元素弹出
st.pop();
// 那结果就是括号外面的结果 + 括号里面的结果，至于是加正数还是负数，取决于左括号外面的符号
res = formerRes +formerSign*res;
}
}
// 返回计算好的结果
return res;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 基本计算器（ LeetCode 224 ）:https://leetcode-cn.com/problems/basic-calculator
class Solution:
def calculate(self, s: str) -> int:
# 使用栈来储存字符串表达式中的数字
stack = list()
# 为了方便计算，所有的操作都视为加法操作
# 那么原先的减法操作就相当于是加一个负数
# 默认都是正数
sign = 1
# 保存计算的结果
res = 0
# 获取字符串的长度，然后获取里面的每个字符
length = len(s)
# 从 0 开始访问字符串中的每个字符
i = 0
# 获取字符串里面的每个字符
while i < length:
# 获取此时的字符
ch = s[i]
if ch == ' ' :
i += 1
# 如果当前字符是数字的话
elif ch.isdigit() :
# 那么把获取到的数累加到结果 res 上
value = ord(s[i]) - ord('0')
# 去查看当前字符的后一位是否存在
# 如果操作并且后一位依旧是数字，那么就需要把后面的数字累加上来
while i + 1 < length and s[i + 1].isdigit():
i += 1
value = value * 10 + ord(s[i]) - ord('0')
# 那么把获取到的数累加到结果 res 上
res += value * sign
i += 1
# 如果是 '+'
elif ch == '+' :
# 那么说明直接加一个正数
sign = 1
i += 1
# 如果是 '-'
elif ch == '-' :
# 那么说明加一个负数
sign = -1
i += 1
# 如果是 '('
elif ch == '(' :
# 根据数学计算规则，需要先计算括号里面的数字
# 而什么时候计算呢？
# 遇到 ) 为止
# 所以，在遇到 ) 之前需要把之前计算好的结果存储起来再计算
# ( ) 直接的计算规则和一开始是一样的
# 1、先把 ( 之前的结果存放到栈中
stack.append(res)
# 2、重新初始化 res 为 0
res = 0
# 3、把 ( 左边的操作符号存放到栈中
# 比如如果是 5 - （ 2 + 3 ） ，那么就是把 -1 存放进去
# 比如如果是 5 +（ 2 + 3 ） ，那么就是把 1 存放进去
stack.append(sign)
# 4、为了方便计算，所有的操作都视为加法操作
# 那么原先的减法操作就相当于是加一个负数
# 默认都是正数
sign = 1
i += 1
# 如果是 ')'
elif ch == ')' :
# 那么就需要把栈中存放的元素取出来了
# 在 ch == '（' 这个判断语句中，每次都会往栈中存放两个元素
# 1、先存放左括号外面的结果
# 2、再存放左括号外面的符号
# 1、先获取栈顶元素，即左括号外面的符号，查看是 + 还是 -
# 把栈顶元素弹出
formerSign = stack.pop()
# 2、再获取栈顶元素，即左括号结果
# 把栈顶元素弹出
formerRes = stack.pop()
# 那结果就是括号外面的结果 + 括号里面的结果，至于是加正数还是负数，取决于左括号外面的符号
res = formerRes + formerSign * res
i += 1
# 返回计算好的结果
return res
# 四、复杂度分析
时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。
空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈中的元素数量不超过 n。
# 五、直接调API解法
如果上述内容实在学得吃力，但机试中又不幸遇到。可以直接使用内置函数eval()解题。内置函数eval()能够直接计算一个字符串表达式的值，能够识别加减乘除以及括号。
s = input()
print(eval(s))